public class MinCostClimbingStairs {
    public int minCostClimbingStair1s(int[] cost) {
        int n = cost.length;
        // 因为楼顶是在 n 位置, 因此 dp 表需要 n+1 个空间
        int[] dp = new int[n+1];

        // 初始化, 防止越界, 第一次开始爬楼梯, 前面是不存在状态的, 因此设置为 0
        dp[0] = dp[1] = 0;
        for(int i = 2; i < n+1; i++) {
            dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }

        // 最后返回到达顶楼位置最低花费
        return dp[n];
    }

    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n];

        dp[n-1] = cost[n-1];
        dp[n-2] = cost[n-2];

        for(int i = n-3; i >= 0; i--) {
            dp[i] = Math.min(dp[i+1] + cost[i], dp[i+2] + cost[i]);
        }

        // 返回从 0 下标或者 1 下标到达顶楼的最小花费
        return Math.min(dp[0], dp[1]);
    }
}
